package org.example.com.corffen.string

/**
 * https://leetcode.cn/problems/zigzag-conversion/description/?envType=problem-list-v2&envId=string
 * 6. Z 字形变换
 * 中等
 * 相关标签
 * 相关企业
 * 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
 *
 * 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
 *
 * P   A   H   N
 * A P L S I I G
 * Y   I   R
 * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
 */
fun convert(s: String, numRows: Int): String {
    val rows = ArrayList<StringBuilder>(numRows)
    repeat(numRows) {
        rows.add(StringBuilder())
    }
    var index = 0
    var flag = false
    for (c in s) {
        rows[index].append(c)
        if (index % (numRows - 1) == 0) {
            flag = !flag
        }
        if (flag) {
            index++
        } else {
            index--
        }
    }
    val sb = StringBuilder()
    rows.forEach {
        sb.append(it)
    }
    return sb.toString()
}

/**
 * chatgpt-->优化的代码
 */
fun convert2(s: String, numRows: Int): String {
    // 特殊情况处理
    if (numRows == 1 || s.length <= numRows) return s

    // 创建字符串构建器列表用于存储每一行的字符
    val rows = Array(numRows) { StringBuilder() }
    var index = 0
    var direction = -1

    // 遍历字符串，按Zigzag模式将字符添加到对应的行
    for (c in s) {
        rows[index].append(c)
        if (index == 0 || index == numRows - 1) direction *= -1
        index += direction
    }

    // 合并所有行的字符到一个字符串中并返回
    return rows.joinToString("")
}

fun myAtoi(s: String): Int {
    val n = s.length
    var i = 0
    while (i < n && s[i] == ' ') i++
    if (i == n) return 0
    val sign = if (s[i] == '-') {
        i++
        -1
    } else if (s[i] == '+') {
        i++
        1
    } else 1
    var res = 0
    while (i < n && s[i] in '0'..'9') {
        val digit = s[i++] - '0'
        if (res > (Int.MAX_VALUE - digit) / 10) {
            return if (sign == 1) Int.MAX_VALUE else Int.MIN_VALUE
        }
        res = res * 10 + digit
    }
    return res * sign
}

/**
 * 数字转换成罗马字母
 */
fun intToRoman(num: Int): String {
    // 定义罗马数字符号及其对应的值
    val romanSymbols = listOf(
        "M" to 1000, "CM" to 900, "D" to 500, "CD" to 400,
        "C" to 100, "XC" to 90, "L" to 50, "XL" to 40,
        "X" to 10, "IX" to 9, "V" to 5, "IV" to 4, "I" to 1
    )
    var remaining = num
    val result = StringBuilder()
    // 从大到小遍历罗马数字符号，逐个添加到结果中
    for ((symbol, value) in romanSymbols) {
        while (remaining >= value) {
            result.append(symbol)
            remaining -= value
        }
    }
    return result.toString()
}

/**
 * 罗马数字转成整数
 * 1. 从后往前遍历
 * 2. 如果当前字符的值小于前一个字符的值，则减去当前字符的值，否则加上当前字符的值
 * 3. 返回最终的结果
 */
fun romanToInt(s: String): Int {
    // 定义罗马数字符号及其对应的值
    val romanMap = mapOf(
        'I' to 1, 'V' to 5, 'X' to 10,
        'L' to 50, 'C' to 100, 'D' to 500, 'M' to 1000
    )
    var result = 0
    var prevValue = 0
    for (c in s.reversed()) {
        val currentValue = romanMap[c] ?: 0
        if (currentValue < prevValue) {
            result -= currentValue
        } else {
            result += currentValue
        }
        prevValue = currentValue
    }
    return result
}
/**
 * 寻找字符串数组中所有字符串的最长公共前缀。
 *
 * @param strs 字符串数组，其中包含了若干字符串。
 * @return 返回这些字符串的最长公共前缀。如果没有公共前缀，返回空字符串。
 */
fun longestCommonPrefix(strs: Array<String>): String {
    if (strs.isEmpty()) return ""
    var prefix = strs[0]
    for (i in 1 until strs.size) {
        while (!strs[i].startsWith(prefix)) {
            prefix = prefix.dropLast(1)
            if (prefix.isEmpty()) return ""
        }
    }
    return prefix
}


